import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(stack.isEmpty()){
                stack.push(ch);
            } else if ((ch == ')' && stack.peek() == '(') || (ch == '}' && stack.peek() == '{') || (ch == ']' && stack.peek() == '[')) {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }

    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();

        int j=0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (stack.peek().equals(popA[j])){
                stack.pop();
                j++;
                if(stack.isEmpty()){
                    break;
                }
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String s:tokens) {
            switch (s){
                case "+":
                    int ret1 = stack.pop();
                    stack.push(ret1+stack.pop());
                    break;
                case "-":
                    int ret2 = stack.pop();
                    stack.push(stack.pop()-ret2);
                    break;
                case "*":
                    int ret3 = stack.pop();
                    stack.push(ret3*stack.pop());
                    break;
                case "/":
                    int ret4 = stack.pop();
                    stack.push(stack.pop()/ret4);
                    break;
                default:
                    int x = Integer.parseInt(s);
                    stack.push(x);
                    break;
            }
        }
        return stack.pop();
    }
}